package com.algorithm.ch1.cjm.dynamic;

/**
 * 爬楼梯
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * <p>
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * <p>
 * 注意：给定 n 是一个正整数。
 *
 */
public class ClimbStairs {

    public static void main(String[] args) {

        long time1 = System.currentTimeMillis();

        for (int i = 0; i < 44; i++) {
            System.out.println("i的值为：" + i + "解一结果为：" + climbStairs(i));
        }

        long time2 = System.currentTimeMillis();

        System.out.println("=======" + "系统耗时： " + (time2 - time1) + "===========");

        for (int i = 0; i < 50; i++) {
            System.out.println("i的值为：" + i + "解二结果为：" + climbStairs1(i));
        }

        long time3 = System.currentTimeMillis();

        System.out.println("=======" + "系统耗时： " + (time3 - time2) + "===========");

        System.out.println(Integer.MAX_VALUE);

    }

    /**
     * 第一版，用了递归，性能太慢
     * @param n
     * @return
     */
    public static int climbStairs(int n) {

        if(n <= 0){
            return 0;
        }

        if(n == 1){
            return 1;
        }else if(n == 2){
            return 2;
        }

        return climbStairs(n -1) + climbStairs(n -2);
    }

    /**
     * 自顶向下的备忘录法
     * 已经求出的子解的值，不用再求
     * @param n
     * @return
     */
    public static int climbStairs2(int n){
        if(n <= 0) {
            return n;
        }
        int[] memo = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            memo[i] = -1;
        }

        return fib(n, memo);
    }

    //递归求解
    public static int fib(int n, int[] memo){

        if(memo[n] != -1) {
            return memo[n];
        }

        if(n <= 2){
            memo[n] = 1;
        }else {
            memo[n] = fib(n - 1, memo) + fib(n -2, memo);
        }

        return memo[n];
    }

    /**
     * 自底向上的动态规划，
     * 把上一步的解放到数组里面
     *
     * @param n
     * @return
     */
    public static int climbStairs1(int n){

        if(n <= 1){
            return 1;
        }

        int[] res = new int[n];
        res[0] = 1;
        res[1] = 2;

        for(int i = 2; i < n; i++){
            res[i] = res[i - 1] + res[i - 2];
        }

        return res[n - 1];
    }

    /**
     * 自底向上的动态规划
     * 优化空间复杂度
     * @param n
     * @return
     */
    public static int fib(int n){

        if(n <= 1) {
            return n;
        }

        int memo2 = 0;
        int memo1 = 1;
        int memo = 1;

        for (int i = 2; i <= n; i++) {
            memo = memo2 + memo1;
            memo2 = memo1;
            memo1 = memo;
        }

        return memo;
    }
}
